/**
 * @Author: linzp
 * @Date: 2022/07/13/17:00
 */
public class demo0713 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        System.out.println(searchInsert2(nums, 2));
//        System.out.println(3/2);
    }

    /**
     * 35. 搜索插入位置
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * <p>
     * 请必须使用时间复杂度为 O(log n) 的算法。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: nums = [1,3,5,6], target = 5
     * 输出: 2
     * 示例 2:
     * <p>
     * 输入: nums = [1,3,5,6], target = 2
     * 输出: 1
     * 示例 3:
     * <p>
     * 输入: nums = [1,3,5,6], target = 7
     * 输出: 4
     */

    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;//左开右闭写法
        while (left < right) {
            int mid = left + ((right - left) >> 2);
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;//因为退出循环的条件是left < right 所以如果right = mid-1 就会错过right这个位置也就是right这个位置没判断到  例nums = [1,3,5,6], target = 2 right=mid-1>=left退出循环就直接返回left了，其实应该再对left做一次判断看看是返回left还是left+1的。
            }
        }
        return left;

    }

    //二分
    public static int searchInsert2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;//左开右闭写法
        while (left <= right) {
            int mid = left + ((right - left)/2);
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;//这里right = mid - 1 是因为判断退出循环的条件是left <= right，所以并不会错过right这个位置的 当right = mid-1 =left时，下一次循环left+1还是会回到right这个位置来
            }
        }
        return left;

    }

    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * <p>
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * <p>
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例 2：
     * <p>
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     * <p>
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     */

    class Solution {
        public  int[] searchRange(int[] nums, int target) {
            int leftindex = getLeftBorder(nums, target);
            int rightindex = getRightBorder(nums, target);
            if (leftindex == -2 || rightindex == -2)
                return new int[] { -1, -1 };
            else
                return new int[] { leftindex + 1, rightindex - 1 };
        }

        // 1233356
        public  int getLeftBorder(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int middle;
            int leftBorder = -2;// 设置初始值
            while (left <= right) {
                middle = (left + right) / 2;
                if (nums[middle] > target) {
                    right = middle - 1;
                } else if (nums[middle] < target) {
                    left = middle + 1;
                } else {// 当相等的时候,更新leftBorder 右边界收缩也就是把target变成右边界，知道最后变成右边界-1退出循环 例如1233 - 123 - 12 输出2
                    right = middle - 1;
                    leftBorder = right;
                }
            }
            return leftBorder;
        }

        public  int getRightBorder(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int middle;
            int rightBorder = -2;
            while (left <= right) {
                middle = (left + right) / 2;
                if (nums[middle] < target) {
                    left = middle + 1;
                } else if (nums[middle] > target) {
                    right = middle - 1;
                } else {// 当相等的时候，更新rightBorder 同理
                    left = middle + 1;
                    rightBorder = left;
                }
            }
            return rightBorder;
        }
    }
}
/**
 * 进行二分搜索
 * 这里就分为两种情况
 *
 * int right = size;
 * int right = size-1;
 * 两种right就有两种while循环，分别对应的是
 *
 * while(left < right)
 * while(left <= right)
 *
 *
 *
 * 这里得知道一个概念——搜索区间
 *
 * 当right = size时，是数组最后一个元素的指针+1，所以搜索区间是[left,right)
 * 左闭右开，所以left不能等于right，最大只能是right-1
 * 所以while(left < right)循环的退出条件是left==right
 * 而此时的left已经最后一个元素的指针+1
 * 或者是上一次循环中已经判断过的mid
 * ————————————————
 *
 * 我的理解：左闭右开 right=mid
 * 是因为right = size,所以wihle(left < right)，left=right是越界搜索了
 * 而退出while的前提是left==right 也就是不符合left < right
 * left最坏的情况的一直++,所以最终等于mid 假如要插入元素那么left就是最终解了
 * right最坏的情况是一直往左靠 right=mid也就是，right最终会等于left，假如要插入元素，那么也是返回left即可。
 * 那为啥不能right--呢，虽然一直往左靠，right最终也会等于left，但假如要插入元素，你只知道了上一个right是判断过为>mid的，那么right=mid-1=left时就会有一个问题，就是
 * 循环已经结束并退出了，你只得到了left，但你并没对这个left做过判断，你怎么知道是插入在left的右边还是left这个位置呢 比如1346 target=2 你最终left=0，那返回0不就错了，应该返回1才对
 * 所以right=mid可以在退出循环前right = mid =left 做最后一次判断而不会跳过right
 * target>mid left++ = right =mid
 * target<mid right = mid = left;
 * return left 就知道返回哪个位置了。
 *
 *
 * 版权声明：本文为CSDN博主「侠義芝士」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/weixin_44797811/article/details/115521784
 */